#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Swap(int* p1, int* p2)
{
	int tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}
void Print(int* p, int n)
{
	for (int i = 0; i < n; i++) {
		printf("%d ", p[i]);
	}
	printf("\n");
}
void InsertSort(int* p, int n)
{
	int end = 0;
	while (end<n-1)
	{
		int key = p[end + 1];
		int i = end;
		while (i >= 0) {
			if (p[i] >=key) {
				p[i + 1] = p[i];
			}
			else {
				break;
			}
			i--;
		}
		Swap(&p[i+1], &key);
		end++;
	}
}
void test()
{
	int arr[] = { 5,4,3,6,5,2,1,7,8,9 };
	int size = sizeof(arr) / sizeof(int);
	InsertSort(arr, size);
	Print(arr, size);
}
int main()
{
	test();

	return 0;
}